#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct node
{
    ElemType data;
    struct node *next;
}Node;

//初始化链表
Node* initList(){
    Node *head = (Node*)malloc(sizeof(Node));
    head->data = 0;
    head->next = NULL;
    return head;
}

//头插法
int insertHead(Node* L,ElemType e){
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = e;
    p->next = L->next;
    L->next = p;
    return 1;
}

void listNode(Node *L){
    Node *p = L->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
   
}

//获取尾部节点
Node* get_tail(Node *L){
    Node* p = L;
    while (p->next != NULL)
    {
        p = p->next;
    }

    return p;
    
}


//尾插法
Node* insertTail(Node *tail, ElemType e){
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = e;
    tail->next = p;
    p->next = NULL;
    return p;
}

//指定位置插入新的节点
int insertNode(Node *L, int pos,  ElemType e){
    Node *p = L;
    int i = 0;

    while (i < pos -1)
    {
        p = p->next;
        i++;
        if(p == NULL){
            return 0;
        }
    }

    //要插入的新节点
    Node *q = (Node*)malloc(sizeof(Node));
    q->data = e;
    q->next = p->next;
    p->next = q;
    return 1;
    
}

int deleteNode(Node* L,int pos){
    Node *p = L;
    int i = 0;

    while (i < pos - 1)
    {
        p = p->next;
        i++;
        if(p == NULL){
            return 0;
        }
    }
    
    if(p->next == NULL)
	{
		printf("要删除的位置错误\n");
		return 0;
	}
	//q指向要删除的节点
	Node *q = p->next;
	//让p的next删除节点的前驱指向要删除节点的后继
	p->next = q->next;
	//释放要删除节点的内存空间
	free(q);
	return 1;


}

//获取链表长度
int get_len(Node *L){
    Node *p = L;
    int len = 0;
    while(p != NULL){
        p = p->next;
        len++;
    }

    return len;
}

//释放链表
int freeList(Node *L){
    Node *p = L->next;
    Node *q;

    while (p != NULL)
    {
        q = p->next;
        free(p);
        p = q;
    }

    L->next = NULL;
    
}

//用快慢指针找到倒数第k个节点上保存的数据
int findNodeFS(Node *L,int k){
    Node *slow = L->next;
    Node *fast = L->next;

    for(int i = 0; i < k; i++){
        fast = fast->next;
    }

    while (fast != NULL)
    {
        fast = fast->next;
        slow = slow->next;
    }


    printf("链表�??倒数�??%d�??节点上的数据�??: %d\n", k, slow->data);
    return 1;
    
}

//初始化化节点（带节点数据域参数）
Node* initListWithElem(ElemType e)
{
	Node *node = (Node*)malloc(sizeof(Node));
	node->data = e;
	node->next = NULL;
	return node;
}

//尾插法（节点�??
Node* insertTailWithNode(Node *tail, Node *node){
    tail->next = node;
    node->next =NULL;

    return node;
}

Node* findIntersectionNode(Node *headA, Node *headB)
{
	if(headA == NULL || headB == NULL)
	{
		return NULL;
	}

	Node *p = headA;
	int lenA = 0;
	int lenB = 0;
	
	//遍历链表A，获取链表A的长度
	while(p != NULL)
	{
		p = p->next;
		lenA++;
	}
	//遍历链表B，获取链表B的长度
	p = headB;
	while(p != NULL)
	{
		p = p->next;
		lenB++;
	}

	Node *m;//快指针
	Node *n;//慢指针
	int step;//两个单词之间数量的差值，可以用于快指针先走的步数
	if (lenA > lenB)
	{
		step = lenA - lenB;
		m = headA;
		n = headB;
	}
	else
	{
		step = lenB - lenA;
		m = headB;
		n = headA;
	}
	//让快指针先走step步
	for (int i = 0; i < step; i++)
	{
		m = m->next;
	}
	//快慢指针同步走，直到指向同一个节点退出循环
	while(m != n)
	{
		m = m->next;
		n = n->next;
	}
	return m;
}

void removeNode(Node *L, int n){
	//其中n是标记用的数组长度
	Node *p = L;
	int index;
	int *q = (int*)malloc(sizeof(int) * (n + 1));


	//遍历数组，先把标记用的数组全部赋值成0
	for(int i = 0; i < n + 1; i++){
		*(q + i) = 0;
	}

	while (p->next != NULL)
	{
		index = abs(p->next->data);
		if(*(q + index) == 0){
			*(q + index) = 1;
			p = p->next;
		}else{
			Node *tmp = p->next;
			p->next = tmp->next;
			free(tmp);
		}
	}

	free(q);
	
}

//反转链表
Node* reverseList(Node* head)
{
	Node *first = NULL;
	Node *second = head->next;
	Node *third;

	while(second != NULL)
	{
		third = second->next;
		second->next = first;
		first = second;
		second = third;
	}
	Node *hd = initList();
	hd->next = first;

	return hd;
}

//删除中间节点
int delMiddleNode(Node *head){
	Node *fast = head->next;
	Node *slow = head;

	while (fast != NULL && fast->next != NULL)
	{
		fast = fast->next->next;
		slow = slow->next;
	}

	Node *q = slow->next;
	slow->next = q->next;
	free(q);
	
	return 1;
}

//链表重新排序
void reOrderList(Node *head)
{
	Node *fast = head->next;
	Node *slow = head;
	while(fast != NULL && fast->next != NULL)
	{
		fast = fast->next->next;
		slow = slow->next;
	}

	Node *first = NULL;
	Node *second = slow->next;
	slow->next = NULL;
	Node *third = NULL;

	while(second != NULL)
	{
		third = second->next;
		second->next = first;
		first = second;
		second = third;
	}

	Node *p1 = head->next;
	Node *q1 = first;
	Node *p2, *q2;
	while(p1 != NULL && q1 != NULL)
	{
		p2 = p1->next;
		q2 = q1->next;

		p1->next = q1;
		q1->next = p2;

		p1 = p2;
		q1 = q2;
	}
}


//判断链表是否有环
int isCycle(Node *head)
{
	Node *fast = head;
	Node *slow = head;

	while(fast != NULL && fast->next != NULL)
	{
		fast = fast->next->next;
		slow = slow->next;
		if (fast == slow)
		{
			return 1;
		}
	}

	return 0;
}

//找到链表环的入口
Node* findBegin(Node *head)
{
	Node *fast = head;
	Node *slow = head;

	while(fast != NULL && fast->next != NULL)
	{
		fast = fast->next->next;
		slow = slow->next;
		if (fast == slow)
		{
			Node *p = fast;
			int count = 1;
			while(p->next != slow)
			{
				count++;
				p = p->next;
			}

			fast = head;
			slow = head;

			for (int i = 0; i < count; i++)
			{
				fast = fast->next;
			}

			while(fast != slow)
			{
				fast = fast->next;
				slow = slow->next;
			}
			return slow;
		}
	}
	return NULL;
}



int main(int argc,char const *argv[]){
    system("chcp 65001");

    // Node *list = initList();
    // Node *tail = get_tail(list);
    //调用头插法插入数据
    // for(int i = 1; i< 8; i++){
    //     insertHead(list, i * 10);
    // }

    //调用尾插法插入数据
    // for(int j = 1;j < 8; j++){
    //     tail = insertTail(tail, j * 10);
    // }

    // listNode(list);

    //从中间某个位置插入数据
    // insertNode(list, 2, 15);
    // listNode(list);
    //删除某个位置的数据
    // deleteNode(list,2);
    // listNode(list);
    //获取链表长度
    // printf("length: %d \n",get_len(list));
    //调用释放链表的函数
    // freeList(list);
    // printf("length: %d \n",get_len(list));


    //调用查找倒数第k个节点的数据的函数
    // findNodeFS(list, 3);

    // Node *listA = initList();
	// Node *listB = initList();
	// Node *tailA = get_tail(listA);
	// Node *tailB = get_tail(listB);
	// tailA = insertTail(tailA, 'l');
	// tailA = insertTail(tailA, 'o');
	// tailA = insertTail(tailA, 'a');
	// tailA = insertTail(tailA, 'd');
	// tailB = insertTail(tailB, 'b');
	// tailB = insertTail(tailB, 'e');

	// Node *nodeI = initListWithElem('i');
	// tailA = insertTailWithNode(tailA, nodeI);
	// tailB = insertTailWithNode(tailB, nodeI);
	// Node *nodeN = initListWithElem('n');
	// tailA = insertTailWithNode(tailA, nodeN);
	// tailB = insertTailWithNode(tailB, nodeN);
	// Node *nodeG = initListWithElem('g');
	// tailA = insertTailWithNode(tailA, nodeG);
	// tailB = insertTailWithNode(tailB, nodeG);

	// listNode(listA);
	// listNode(listB);

	// printf("%c\n",findIntersectionNode(listA,listB)->data);


	//移除绝对值相等的节点
	// Node *list = initList();
	
	// Node *tail = get_tail(list);
	
	// tail = insertTail(tail, 21);
	// tail = insertTail(tail, -15);
	// tail = insertTail(tail, -15);
	// tail = insertTail(tail, 7);
	// tail = insertTail(tail, 15);
	// listNode(list);
	// removeNode(list,21);


	//调用反转链表的函数
	// Node *list = initList();
	
	// Node *tail = get_tail(list);
	
	// for(int i = 0; i < 10; i++){
	// 	tail = insertTail(tail, i);
	// }
	// listNode(list);

	// Node* reverse = reverseList(list);
	// listNode(reverse);

	//调用删除中间节点的函数
	// Node *list = initList();
	
	// Node *tail = get_tail(list);
	
	// for(int i = 0; i < 10; i++){
	// 	tail = insertTail(tail, i);
	// }



	// listNode(list);
	// delMiddleNode(list);
	// listNode(list);

	//调用让链表重新排序的函数
	// Node *list = initList();
	
	// Node *tail = get_tail(list);
	
	// tail = insertTail(tail, 1);
	// tail = insertTail(tail, 2);
	// tail = insertTail(tail, 3);
	// tail = insertTail(tail, 4);
	// tail = insertTail(tail, 5);
	// tail = insertTail(tail, 6);
	
	// listNode(list);
	// reOrderList(list);
	// listNode(list);

	//调用判断链表是否有环的函数
	Node *list = initList();
	
	Node *tail = get_tail(list);
	
	tail = insertTail(tail, 1);
	tail = insertTail(tail, 2);
	tail = insertTail(tail, 3);
	Node *three = tail;
	tail = insertTail(tail, 4);
	tail = insertTail(tail, 5);
	tail = insertTail(tail, 6);
	tail = insertTail(tail, 7);
	tail = insertTail(tail, 8);
	tail->next = three;

	//listNode(list);
	
	if (isCycle(list))
	{
		printf("有环\n");
	}
	else
	{
		printf("无环\n");
	}
	//调用找到环的入口的函数
	Node *p = findBegin(list);
	printf("%d\n", p->data);

    return 0;
}
